package pro.softzhang.algo.lc2100;

import pro.softzhang.algo.flag.difficulty.DRed;
import pro.softzhang.algo.flag.x.XOptimal;

/**
 *
 */
@DRed
public class LC2106_MaximumFruitsHarvestedAfterAtMostKSteps {
    public static void main(String[] args) {

    }

    /**
     * 完全是抄的
     * https://leetcode.cn/problems/maximum-fruits-harvested-after-at-most-k-steps/solution/python3javacgotypescript-yi-ti-yi-jie-sh-59o2/
     */
    @XOptimal
    static
    class Solution {
        public int maxTotalFruits(int[][] fruits, int startPos, int k) {
            int max = 0, s = 0;
            for (int i = 0, j = 0; j < fruits.length; ++j) {
                int pj = fruits[j][0], fj = fruits[j][1];
                s += fj;
                while (i <= j && pj - fruits[i][0] + Math.min(Math.abs(startPos - fruits[i][0]), Math.abs(startPos - pj)) > k) {
                    s -= fruits[i++][1];
                }
                max = Math.max(max, s);
            }
            return max;
        }
    }
}
